public class MyLinkedList {
    public ListNode head;//头节点
    public ListNode last;//尾节点
    static class ListNode{//内部类里面是节点的基本组成
        private int val;
        private ListNode next;
        private ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }
    public int size(){//计算链表的大小
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    public void display(){//展示链表的内容
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();


    }
    public boolean contains(int key){//判断链表中是否有某个值
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;

            }
            cur=cur.next;
        }
        return false;

    }
    public void addFirst(int data){//头插法
        ListNode node=new ListNode(data);
        if(head==null){
            head=node;
            last=node;

        }else{
            node.next = head;
            head = node;

        }
    }
    public  void addLast(int data){//尾插法
        ListNode node=new ListNode(data);
        if(head==null){
            head=node;

        }else{
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }
    public void addIndex(int index,int data){
        if(index<0||index>size()){
            System.out.println("index 不合法！");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
        }
        ListNode cur =findIndexSubOne(index);
            ListNode node =new ListNode(data);
            node.next=cur.next;
            cur.next=node;




    }
    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        while (index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public  void  remove(int key){
        if(head==null){
            return;

        }
        if(head.val==key){
            head=head.next;
            return;
        }
        ListNode cur =searchPrev(key);
            if(cur==null){
                System.out.println("没有你要删除的数字");
                return;
            }
            ListNode del=cur.next;
            cur.next=del.next;
        }
    public  ListNode searchPrev(int key) {
        ListNode cur = head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;

    }
    public void removeAllKey(int key){
        ListNode pre=head;
        ListNode cur=head.next;
        if(head==null){
            return;
        }
        while(cur!=null){
            if(cur.val==key){
                pre.next=cur.next;
                cur=cur.next;

            }else{
                pre=cur;
                cur=cur.next;
            }
        }
        if(head.val==key){
            head=head.next;
        }
    }
    public  void clear(){
        this.head=null;
    }

}
